<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        // https://www.bilibili.com/video/BV1Eb41147dK?from=search&seid=4929239766443836928
        // function heapSort(array) {
        //     //1、创建最大堆：从最后一个节点的父节点开始调整堆 这个是关键
        //     let len = array.length - 1;
        //     let lastIndex = Math.floor((len - 1) / 2); //公式 找子节点的父节点
        //     for (let i = lastIndex; i >= 0; i--) {
        //         maxHeap(array, len, i); //从最后一个父节点开始层层向上 进行调整堆
        //     }
        //     for (let i = len; i >= 0; i--) {
        //         let temp = array[0];
        //         array[0] = array[i];
        //         array[i] = temp;
        //         maxHeap(array, i, 0); //去掉已排好序的节点，剩余节点重新构堆。
        //     }
        // }

        // function maxHeap(array, heapSize, index) { //从最后一个子节点到第index节点构堆
        //     //左子节点
        //     let leftChild = 2 * index + 1; //公式
        //     //右子节点
        //     let rightChild = 2 * index + 2; //公式 
        //     //最大元素下标
        //     let largestIndex = index;
        //     //分别比较当前假设的最大节点和它的左右节点，找出最大值
        //     if (leftChild < heapSize && array[leftChild] > array[largestIndex]) {
        //         largestIndex = leftChild;
        //     }
        //     if (rightChild < heapSize && array[rightChild] > array[largestIndex]) {
        //         largestIndex = rightChild;
        //     }
        //     if (largestIndex !== index) {
        //         let temp = array[largestIndex];
        //         array[largestIndex] = array[index];
        //         array[index] = temp;
        //         //交换后，其子节点可能就不是最大堆了，需要对交换后的子节点重新调整
        //         maxHeap(array, heapSize, largestIndex)
        //     }
        // }
        // let array = [23, 4, 12, 8, 5, 26, 3, 4, 1];
        // heapSort(array);
        // console.log(array); //[1,3,4,4,5,8,12,23,26]
    </script>





    <script>
        function headSorts(arr) {
            let len = arr.length;
            let lastIndex = Math.floor((len - 1 - 1) / 2);
            for (let i = lastIndex; i >= 0; i--) {
                maxHead(arr, len, i);
            }
            for (let i = len - 1; i >= 0; i--) {
                let temp = arr[0];
                arr[0] = arr[i];
                arr[i] = temp;
                maxHead(arr, i, 0);
            }
        }

        function maxHead(arr, headSize, i) {
            let left = 2 * i + 1;
            let right = 2 * i + 2;
            let largestIndex = i;
            if (left < headSize && arr[left] > arr[largestIndex]) {
                largestIndex = left;
            }
            if (right < headSize && arr[right] > arr[largestIndex]) {
                largestIndex = right;
            }
            if (largestIndex !== i) {
                let temp = arr[largestIndex];
                arr[largestIndex] = arr[i];
                arr[i] = temp;
                maxHead(arr, headSize, largestIndex);
            }
        }
        let arr = [3, 1, 2, 4, 5];
        headSorts(arr)
        console.log(arr);
        console.log(arr[arr.length - 2]);
    </script>
</body>

</html>